图神经网络导论


机器学习 下

计算机科学与技术学院     张腾


tengzhang@hust.edu.cn


大纲

g 人工智能 人工智能 逻辑推理 逻辑推理 人工智能->逻辑推理 知识工程 知识工程 人工智能->知识工程 机器学习 机器学习 人工智能->机器学习 监督信息 监督信息 机器学习->监督信息 模型方法 模型方法 机器学习->模型方法 监督学习 监督学习 监督信息->监督学习 半监督学习 半监督学习 监督信息->半监督学习 无监督学习 无监督学习 监督信息->无监督学习 离散 分类 离散 分类 监督学习->离散 分类 连续 回归 连续 回归 监督学习->连续 回归 聚类 聚类 无监督学习->聚类 降维 嵌入 降维 嵌入 无监督学习->降维 嵌入 密度估计 密度估计 无监督学习->密度估计 A …… B …… C …… 模型方法->A 模型方法->B 模型方法->C


监督学习

所有样本都有类别标记

原始数据 样本 属性特征 类别标记
$o_1$ $(\xv_1, y_1)$ $\xv_1[1:d]$ $y_1$
$o_2$ $(\xv_2, y_2)$ $\xv_2[1:d]$ $y_2$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_m$ $(\xv_m, y_m)$ $\xv_m[1:d]$ $y_m$

任务类型:

  • 二分类:$y \in \{ 1, -1 \}$或者$y \in \{ 0,1 \}$
  • 多分类:$y \in [C] \triangleq \{ 1, 2, \ldots, C \}$
  • 回归:$y \in \Rbb$
  • 结构预测:$y$可以是向量、序列、语法树、……

监督学习 二分类示例

监督学习 多分类示例

监督学习 混淆矩阵

监督学习 回归

线性回归:用最小二乘求解超定方程组 (方程个数比未知数多)


半监督学习

只有部分样本有类别标记,如何利用其它未标记样本?

原始数据 样本 属性特征 类别标记
$o_1$ $(\xv_1, y_1)$ $\xv_1[1:d]$ $y_1$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_l$ $(\xv_l, y_l)$ $\xv_m[1:d]$ $y_l$
$o_{l+1}$ $(\xv_{l+1}, \NULL)$ $\xv_{l+1}[1:d]$ $\NULL$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_{l+u}$ $(\xv_{l+u}, \NULL)$ $\xv_{l+u}[1:d]$ $\NULL$

任务类型:

  • 直推式 (transductive) 学习:预测$\xv_{l+1}, \ldots, \xv_{l+u}$的类别标记,可以没有显式模型
  • 归纳 (inductive) 学习:必须有显式模型,能对未知样本进行预测,包含前者

无监督学习

所有样本都没有类别标记

原始数据 样本 属性特征 类别标记
$o_1$ $(\xv_1, \NULL)$ $\xv_1[1:d]$ $\NULL$
$o_2$ $(\xv_2, \NULL)$ $\xv_2[1:d]$ $\NULL$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_m$ $(\xv_m, \NULL)$ $\xv_m[1:d]$ $\NULL$

任务类型:

  • 聚类:$\xv_i \mapsto c_i \in [K]$,根据一定的准则将样本划分成$K$个簇 (cluster)
  • 降维或嵌入:$\xv_i \mapsto \zv_i \in \Rbb^l$,为样本学习新的特征,自编码 (autoencoder)
  • 密度估计:估计样本空间的概率密度$P(\xv)$,寻找数据的生成机制

无监督学习 聚类
  • 原始数据由 6 个簇组成
  • K 均值算法指定聚成 4 个簇,每种颜色对应一个簇,菱形为簇中心
  • 红色和蓝色各由 2 个簇组成

无监督学习 密度估计
  • 直方图是最简单的密度估计方法,数数即可,对间隔的选择极其敏感
  • 核密度估计:$\rho(\zv) = \sum_{i \in [m]} \kappa ((\zv-\xv_i)/h)$

无监督学习 密度估计
  • 直方图是最简单的密度估计方法,数数即可,对间隔的选择极其敏感
  • 核密度估计:$\rho(\zv) = \sum_{i \in [m]} \kappa ((\zv-\xv_i)/h)$

形式化

常用概念及其符号:

  • $\Xcal \subseteq \Rbb^d$为输入空间,$d$称为维度 (dimension)
  • $\Ycal$为输出空间,对于分类问题$\Ycal = \{ 0,1 \} \mid \{ \pm 1 \} \mid [C]$,对于回归问题$\Ycal = \Rbb$
  • $\Dcal$为定义在$\Xcal \times \Ycal$上的未知分布
  • $\Scal = \{(\xv_1, y_1), \ldots, (\xv_m, y_m)\}$为独立同分布 (IID) 采样于$\Dcal$的训练数据集
  • $\Hcal = \{ h: \Xcal \mapsto \Ycal \}$是候选分类器构成的假设空间,从中选择最优假设$h^\star$

如何评估假设$h$的好坏?$h$在整个分布$\Dcal$上的表现


目标:最小化期望风险,也称为泛化风险

$$ \begin{align*} \min_{h \in \Hcal} ~ \color{red}{R(h)} = \Ebb_{(\xv, y) \sim \Dcal}[1_{h(\xv) \neq y}] \end{align*} $$

难点:$\Dcal$未知,泛化风险无法计算,可以计算$h$$\Scal$上的经验风险


经验风险最小化

以训练数据上的经验风险替代泛化风险

$$ \begin{align*} \class{red}{R(h)} = \Ebb_{(\xv, y) \sim \Dcal}[1_{h(\xv) \neq y}] ~ \longleftarrow ~ \class{blue}{R_\Scal (h)} = \frac{1}{m} \sum_{i \in [m]} 1_{h(\xv_i) \neq y_i} \end{align*} $$

根据大数定律,当样本数趋向于无穷时,经验风险趋向于泛化风险


如果对假设空间不做任何限制,可能会得到

$$ \begin{align*} h(\xv) = - \prod_{i \in [m]: y_i = 1} \| \xv -\xv_i \|^2 \end{align*} $$

问题:

  • 对正类输出零,对负类输出负数,经验风险为零
  • 对未知样本的预测非常糟糕,因为它只是在强行记住见过的训练样本

过拟合

启示:在经验风险和假设空间复杂度之间取得平衡


问题:假设空间复杂度怎么算?有什么量能够刻画它?


VC 维

基本思想:假设空间复杂度应体现出对数据集的拟合能力


假设空间$\Hcal = \{ h: \Xcal \mapsto \{1,-1\} \}$,数据集$S = \{\xv_1, \ldots, \xv_m\}$,定义

$$ \begin{align*} H_\Scal = \{ (h(\xv_1), \ldots, h(\xv_m)) \mid h \in \Hcal \} \end{align*} $$

其中$H_\Scal$中每个元素都是对$S$赋予类别标记的可能结果,若$H_\Scal$包含了全部可能的结果,即$|H_\Scal| = 2^m$,则称假设空间$\Hcal$可以打散数据集$\Scal$


假设空间$\Hcal$VC 维是能被$\Hcal$打散的最大集合的大小,即

$$ \begin{align*} \VC(\Hcal) = \max \{ m \mid \exists S:~|H_\Scal| = 2^m \} \end{align*} $$


VC 维

基本思想:假设空间复杂度应体现出对数据集的拟合能力


二维平面上的线性划分:$\Xcal = \Rbb^2$$\Hcal$为二维平面上直线集合

  • 存在 3 个样本构成的集合,8 种可能类别标记赋值均是线性可分的
  • 对于任意 4 个样本构成的集合,总有一种类别标记赋值线性不可分
  • $\Hcal$的 VC 维为 3
  • $\Rbb^n$中超平面集合的 VC 维为$n+1$

VC 维

根据集中度不等式有如下泛化界

$$ \begin{align*} \class{red}{\underbrace{R(h)}_{泛化风险}} \leq \class{blue}{\underbrace{R_\Scal(h)}_{经验风险}} + \class{yellow}{\underbrace{\tilde{O} \left(\sqrt{\VC维/样本数~~~~~~~~~~}~ \right)}_{置信区间}} \end{align*} $$


结构风险最小化
  • 构造嵌套的假设空间序列
    $\Hcal_1 \subseteq \cdots \subseteq \Hcal_t \subseteq \cdots$
  • 在$\Hcal_t$上经验风险最小化得到$h_t$,$R_\Scal (h_1) \geq \cdots \geq R_\Scal (h_t) \geq \cdots$
  • VC维序列
    $\VC(\Hcal_1) \leq \cdots \leq \VC(\Hcal_t) \leq \cdots$
  • $h^\star = \min_{h_t} \{ \class{blue}{经验风险} + \class{yellow}{置信区间} \}$

问题:

  • 如何计算$\VC(h_t)$$\Xcal$无穷维,$\Hcal_t$超平面集合,$\VC$维无穷?
  • 若假设空间$\Hcal_t$为超平面集合,当维度趋向于无穷时,VC 维也趋向于无穷

间隔和宽打散维

启示:VC 维分布无关、数据独立,导出的泛化界有点“松”

方案:引入数据相关的量加强泛化界,在无穷维空间也可以学习


设$\Hcal = \{ h: \Xcal \mapsto \Rbb \}$是定义在特征空间$\Xcal$上的实值函数集合,对于$\forall h \in \Hcal$,其关于样本$(\xv_i, y_i)$的间隔定义为$\gamma_i = y_i f(\xv_i)$


若对数据集$\Scal$的任一类别标记赋值,均存在假设$h \in \Hcal$和$\gamma > 0$使得$y_i h(\xv_i) \ge \gamma$,则称$\Scal$被$\Hcal$以$\gamma$打散,$\Hcal$的宽打散维$\mathrm{fat}_\Fcal(\gamma)$是能被$\Hcal$以$\gamma$打散的最大集合的大小

特别的,取$\Hcal = \{ \xv \mapsto \wv^\top \xv \mid \|\wv\| = 1 \}$,则能将$\Scal$以$\gamma$打散的超平面称为$\gamma$-间隔超平面,即对$\forall i \in [m]$有$y_i \wv^\top \xv_i \ge \gamma$


$\gamma$-间隔超平面

若数据集包含于一个半径为$R$的球,则$\gamma$-间隔超平面构成的假设空间$\Hcal = \{ \xv \mapsto \wv^\top \xv \mid \|\wv\| = 1 \}$的宽打散维$\mathrm{fat}_\Hcal(\gamma) \leq R^2 / \gamma^2$

物理量 对假设空间的限制 泛化界的大小
VC 维 无穷
宽打散维 有限

最大间隔准则

间隔$\gamma$越大,宽打散维越小,泛化界越紧


最大间隔准则:最小化经验风险 $\wedge$ 最大化间隔

$$ \begin{align*} \max_{\wv} \quad - \lambda \cdot \class{blue}{0} + \class{green}{\gamma} \qquad & \st \quad y_i \wv^\top \xv_i / \|\wv\| \geq \gamma,~ \forall i \in [m] \\ & \Updownarrow \notag \\ \max_{\wv} \quad \hat{\gamma} / \|\wv\| \qquad & \st \quad y_i \wv^\top \xv_i \geq \hat{\gamma},~ \forall i \in [m] \\ & \Updownarrow \notag \\ \max_{\wv} \quad 1 / \|\wv\| \qquad & \st \quad y_i \wv^\top \xv_i \geq 1,~ \forall i \in [m] \\ & \Updownarrow \notag \\ \min_{\wv} \quad \|\wv\| \qquad & \st \quad y_i \wv^\top \xv_i \geq 1,~ \forall i \in [m] \end{align*} $$

即等价于在$1$-间隔超平面构成的假设空间中寻找最小范数假设


正则化

g 限制假设空间 限制假设空间 VC维 VC维 限制假设空间->VC维 宽打散维 宽打散维 VC维->宽打散维 加强 最大间隔准则 最大间隔准则 宽打散维->最大间隔准则 最小范数假设 最小范数假设 最大间隔准则->最小范数假设 $$ \begin{align*} \min_\wv ~ \lambda \cdot \underbrace{\Omega(\wv)}_{正则化项} + \underbrace{R_\Scal (\wv)}_{经验风险} \end{align*} $$

  • $\ell_2$正则:$\Omega(\wv) = \| \wv \|_2^2$,得到稠密的$\wv$
  • $\ell_1$正则:$\Omega(\wv) = \| \wv \|_1$,得到稀疏的$\wv$,附带特征选择的作用
  • $\ell_\infty$正则:$\Omega(\wv) = \| \wv \|_\infty$,得到所有分量值相同的$\wv$
  • $\ell_{2,1}$正则:$\Omega(\wv) = \sum_j \| \wv_j \|_2$,特征分组,组内稠密,组间稀疏
  • $\ell_{1,2}$正则:$\Omega(\wv) = (\sum_j \| \wv_j \|_1)^2$,特征分组,组内稀疏,组间稠密
  • 弹性网:$\ell_1$正则和$\ell_2$正则的线性组合
  • OSCAR:$\ell_1$正则和成对$\ell_\infty$正则的线性组合

假设不成立?特征空间不存在$\gamma$-间隔超平面


非线性映射

问题:输入空间若不存在$\gamma$-间隔超平面?


方案:将数据映射到新的特征空间使其尽量线性可分

$$ \begin{align*} f(\xv; \wv, b) = \wv^\top \xv + b ~ \longrightarrow ~ f(\xv; \wv, b) = \wv^\top [\phi_1(\xv); \ldots; \phi_K(\xv)] + b \end{align*} $$

  • $\wv, b$是待学习的参数
  • $\phi_k: \Rbb^d \mapsto \Hbb$是非线性映射

问题:

  • 很难确定什么样的非线性映射能保证样本在新的特征空间线性可分
  • 即便恰好找到了使得样本线性可分的映射,如何确定其没有引起过拟合

方案:允许约束$y_i \wv^{\top} \xv_i \geq 1$对少数样本不成立


替代损失

基本思想:允许约束$y_i \wv^{\top} \xv_i \geq 1$对少数样本不成立

$$ \begin{align*} \min_{\wv} ~ \lambda \cdot \underbrace{\Omega(\wv)}_{正则化项} + \frac{1}{m} \underbrace{\sum_{i \in [m]} 1_{y_i \wv^\top \xv_i < 1} }_{破坏约束的样本数} \end{align*} $$

难点:指示函数$1_{\cdots}$非凸非连续,导致问题很难求解

方案:用另一个函数$l(y, f(\xv))$替代,称为替代损失,一般需满足

  • 数学性质好,问题容易求解,例如凸连续函数
  • 是指示函数$1_{y \cdot h(\xv) < 0}$的上界,从而利用集中度不等式可得到泛化界:

$$ \begin{align*} & \class{red}{R (h)} = \Ebb_{(\xv, y) \sim \Dcal} [ 1_{y \cdot h(\xv) < 0} ] \leq \Ebb_{(\xv, y) \sim \Dcal} [ l(y, h(\xv)) ] \\ & ~~ \leq \class{blue}{\frac{1}{m} \sum_{i \in [m]} l(y_i, f(\xv_i))} + [ ~ \class{yellow}{\text{VC}} \mid \class{yellow}{\text{Rademacher}} \mid \class{yellow}{\text{covering number}} \mid \ldots ~ ] \end{align*} $$


替代损失

基本思想:允许约束$y_i \wv^{\top} \xv_i \geq 1$对少数样本不成立

$$ \begin{align*} \min_{\wv} ~ \lambda \cdot \underbrace{\Omega(\wv)}_{正则化项} + \frac{1}{m} \underbrace{\sum_{i \in [m]} l(y_i, f(\xv_i))}_{替代损失} \end{align*} $$

凸连续函数,指示函数$1_{y \cdot h(\xv) < 0}$的上界

常见替代损失

  • 平方损失:$l(y, f(\xv)) = (y - f(\xv))^2$,岭回归
  • hinge 损失:$l(y, f(\xv)) = \max \{ 0, 1 - y f(\xv) \}$,软间隔支持向量机
  • 平方 hinge 损失:$l(y, f(\xv)) = [\max \{ 0, 1 - y f(\xv) \}]^2$
  • $\epsilon$-不敏感损失:$l(y, f(\xv)) = \max \{ 0, |y - f(\xv)| - \epsilon \}$,支持向量回归
  • 指数损失:$l(y, f(\xv)) = \exp (- y f(\xv))$
  • 对数几率损失:$l(y, f(\xv)) = \log (1 + \exp (- y f(\xv)))$,对数几率回归

模型求解

即采用优化算法求出如下优化问题的最优解

$$ \begin{align*} \min_\wv ~ F(\wv) \triangleq \lambda \cdot \Omega(\wv) + \frac{1}{m} \sum_{i \in [m]} l(y_i, f(\xv_i)) \end{align*} $$

梯度下降 (GD):$\wv_{t+1} \leftarrow \wv_t - \eta_t \nabla F(\wv_t)$,其中$\eta_t$称为步长或学习率


问题:当样本数$m$很大时,梯度$\nabla F(\wv_t)$计算开销很大

方案:小批量梯度下降,随机采样一个下标子集$\Bcal_t \subseteq [m]$

$$ \begin{align*} \wv_{t+1} \leftarrow \wv_t - \eta_t \left( \frac{1}{|\Bcal_t|} \sum_{i \in \Bcal_t} \nabla l(y_i, f(\xv_i)) + \lambda \cdot \nabla \Omega(\wv) \right) \end{align*} $$

$|\Bcal_t| = 1$,则为常说的随机梯度下降 (SGD)


梯度下降解最小二乘

GD vs. SGD

更新公式:

$$ \begin{align*} & \wv_{t+1} \leftarrow \wv_t - \eta_t \left( \frac{1}{m} \sum_{i \in [m]} \nabla l(y_i, f(\xv_i)) + \lambda \cdot \nabla \Omega(\wv) \right) \\ & \wv_{t+1} \leftarrow \wv_t - \eta_t \left( \frac{1}{|\Bcal_t|} \sum_{i \in \Bcal_t} \nabla l(y_i, f(\xv_i)) + \lambda \cdot \nabla \Omega(\wv) \right) \end{align*} $$

  • 当数据集中有冗余样本时,SGD 可以减少重复计算
  • 迭代前期,SGD 更新频率快,较 GD 优势明显
  • 迭代后期,GD 会停止于最优解处,SGD 则只能在最优解附近震荡
  • 越靠近最优解,梯度越接近零,因此 GD 可以用恒定步长
  • 最优解处随机梯度不一定为零,故 SGD 必须用衰减步长,否则算法不会停止
  • SGD 因随机采样带来的噪声若能随着迭代而受到抑制,则可进一步加速,机器学习顶会有大量相关工作,包括 SAG,SAGA,SVRG 等及其它们的衍生变种

加速梯度下降

当目标函数的变量尺度不同时,梯度下降效率很低

动量法 (momentum):$\wv_{t+1} = \wv_t - \eta_t \nabla F(\wv_t) + \gamma (\wv_t - \wv_{t-1})$

  • 相对于梯度下降,多了第三项,上一轮的更新方向
  • 参数$\gamma < 1$,通常取$0.9$

动量法

$$ \begin{align*} \wv_{t+1} - \wv_t & = - \eta_t \nabla F(\wv_t) + \gamma (\wv_t - \wv_{t-1}) \\ \gamma (\wv_t - \wv_{t-1}) & = - \eta_{t-1} \gamma \nabla F(\wv_{t-1}) + \gamma^2 (\wv_{t-1} - \wv_{t-2}) \\ & \vdots \\ \gamma^{t-1} (\wv_2 - \wv_1) & = - \eta_1 \gamma^{t-1} \nabla F(\wv_1) + \mathtip{\gamma^t (\wv_1 - \wv_0)}{因为\wv_1 = \wv_0,故该项等于零} \\ \Longrightarrow ~ \wv_{t+1} - \wv_t & = - \sum_{i \in [t]} \eta_i \gamma^{t-i} \nabla F(\wv_i) \end{align*} $$

动量法每步更新是历史梯度的加权平均

  • 若近期梯度方向不太一致,则真实的更新幅度变小,减速,增加稳定性
  • 若近期梯度方向较为一致,则真实的更新幅度变大,加速,加快收敛

Nesterov 加速梯度 (NAG):改进动量法的第二步

$$ \begin{align*} \begin{cases} \widetilde{\wv} = \wv_t + \gamma (\wv_t - \wv_{t-1}) \\ \wv_{t+1} = \widetilde{\wv} - \eta_t \class{yellow}{\nabla F (\wv_t)} \end{cases} ~ \longrightarrow ~ \begin{cases} \widetilde{\wv} = \wv_t + \gamma (\wv_t - \wv_{t-1}) \\ \wv_{t+1} = \widetilde{\wv} - \eta_t \class{yellow}{\nabla F (\widetilde{\wv})} \end{cases} \end{align*} $$


动量法 vs. NAG

$t$轮迭代示意图:


大纲

g 人工智能 人工智能 逻辑推理 逻辑推理 人工智能->逻辑推理 知识工程 知识工程 人工智能->知识工程 机器学习 机器学习 人工智能->机器学习 监督信息 监督信息 机器学习->监督信息 模型方法 模型方法 机器学习->模型方法 A …… B …… 监督信息->A 监督信息->B 线性回归 线性回归 模型方法->线性回归 感知机 感知机 模型方法->感知机 支持向量机 支持向量机 模型方法->支持向量机 对数几率回归 对数几率回归 模型方法->对数几率回归 神经网络 神经网络 模型方法->神经网络 卷积神经网络 卷积神经网络 神经网络->卷积神经网络 图像 循环神经网络 循环神经网络 神经网络->循环神经网络 序列 图神经网络 图神经网络 神经网络->图神经网络


线性回归

正则化项 + 损失函数:

$$ \begin{align*} \min_\wv ~ \lambda \cdot \Omega(\wv) + \frac{1}{m} \sum_{i \in [m]} l(y_i, f(\xv_i)) \end{align*} $$

  • 线性模型:$f(\xv) = \wv^\top \xv + b$
  • 平方损失:$l(y, f(\xv)) = (y - f(\xv))^2$
  • 正则化项:无,即采用经验风险最小化

$$ \begin{align*} \min_{\wv,b} ~ \frac{1}{2} \sum_{i \in [m]} (\wv^\top \xv_i + b - y_i)^2 = \frac{1}{2} \| \Xv^\top \uv - \yv \|_2^2 \end{align*} $$

其中$\yv = [y_1; \cdots; y_m]$$\uv \triangleq [\wv; b]$$\Xv = \begin{bmatrix} \xv_1 & \xv_2 & \cdots & \xv_m \\ 1 & 1 & \cdots & 1 \end{bmatrix}$


岭回归

$$ \begin{align*} \min_{\uv} ~ F(\uv) \triangleq \frac{1}{2} \| \Xv^\top \uv - \yv \|_2^2 = \frac{1}{2} \uv^\top \Xv \Xv^\top \uv - \uv^\top \Xv \yv + \frac{1}{2} \yv^\top \yv \end{align*} $$

易知$\nabla F(\uv) = \Xv \Xv^\top \uv - \Xv \yv$

  • $\Xv \Xv^\top$可逆,可得最优解$\uv^\star = (\Xv \Xv^\top)^{-1} \Xv \yv$
  • $\Xv \Xv^\top$不可逆,可采用梯度下降$\uv_{t+1} \leftarrow \uv_t - \eta_t \Xv (\Xv^\top \uv_t - \yv)$进行求解

$\Xv \Xv^\top$近似不可逆时,其最小特征值接近零,模型会变得不稳定:

$$ \begin{align*} \uv^\star = (\Xv \Xv^\top)^{-1} \Xv \yv \longrightarrow \uv^\star = (\Xv \Xv^\top + \lambda \Iv)^{-1} \Xv \yv \end{align*} $$

修正后的解对应带$\ell_2$正则的线性回归,亦称为岭 (ridge) 回归:

$$ \begin{align*} \min_{\uv} ~ \frac{\lambda}{2} \|\uv\|_2^2 + \frac{1}{2} \| \Xv^\top \uv - \yv \|_2^2 \end{align*} $$


LASSO

正则化项 + 损失函数:

$$ \begin{align*} \min_\wv ~ \lambda \cdot \Omega(\wv) + \frac{1}{m} \sum_{i \in [m]} l(y_i, f(\xv_i)) \end{align*} $$

  • 线性模型:$f(\xv) = \wv^\top \xv$
  • 平方损失:$l(y, f(\xv)) = (y - f(\xv))^2$
  • 正则化项:$\ell_1$正则

$$ \begin{align*} \min_\wv ~ \lambda \| \wv \|_1 + \frac{1}{2} \| \Xv^\top \wv - \yv \|_2^2 \end{align*} $$

  • 全称叫最小绝对收缩选择算子 (Least Absolute Shrinkage and Selection Operator)
  • 它求得的$\wv$只有极少数非零分量,因此附带特征选择的作用

感知机

正则化项 + 损失函数:

$$ \begin{align*} \min_\wv ~ \lambda \cdot \Omega(\wv) + \frac{1}{m} \sum_{i \in [m]} l(y_i, f(\xv_i)) \end{align*} $$

  • 线性模型:$f(\xv) = \wv^\top \xv$
  • 损失函数:$l(y, f(\xv)) = \max \{ 0, - y \wv^\top \xv \}$该损失不是指示函数的上界
  • 正则化项:无,即采用经验风险最小化

$$ \begin{align*} \min_\wv ~ F(\wv) \triangleq \frac{1}{m} \sum_{i \in [m]} \max \{ 0, - y_i \wv^\top \xv_i \} \end{align*} $$

目标函数$F(\wv)$关于$(\xv_i, y_i)$的随机次梯度为$\frac{\partial F(\wv)}{\partial \wv} = - y_i \xv_i 1_{y_i \wv^\top \xv_i < 0}$


感知机

算法即为采用随机次梯度下降进行求解的过程

输入:训练集$\{ (\xv_1, y_1), \ldots, (\xv_m, y_m) \}$,迭代次数$T$$\wv_0 \leftarrow \zerov$$k \leftarrow 0$

  1. for $t = 1, \ldots, T$ do
  2.   随机对训练样本进行排序
  3.   for $i = 1, \ldots, m$ do
  4.     if $y_i \wv_k^\top \xv_i < 0$ then
  5.       $\wv_{k+1} \leftarrow \wv_k + y_i \xv_i$
  6.       $k \leftarrow k + 1$
  7.     end
  8.   end
  9. end

输出:$\wv_k$


感知机

在线性可分的数据上,感知机必然可以收敛:

给定训练集$\Scal = \{ (\xv_i, y_i) \}_{i \in [m]}$,如果$\Scal$线性可分,即存在$\gamma > 0$和$\wv$使得对$\forall i \in [m]$有$y_i \wv^\top \xv_i \geq \gamma$,设$r = \max_i \| \xv_i \|$,则感知机的权重更新次数不超过$r^2 / \gamma^2$


不足之处:

  • 感知机虽然可以找到一个超平面把两类数据分开,但并不能保证泛化能力
  • 感知机对接收的样本顺序敏感,当顺序发生变化时求得的分类超平面也会随之变化
    改进方案:投票感知机,输出迭代过程中的所有$\wv_k$的线性组合,正确分类样本次数越多的$\wv_k$,系数越大
  • 如果训练集不是线性可分的,感知机永远不会收敛

支持向量机

正则化项 + 损失函数:

$$ \begin{align*} \min_\wv ~ \lambda \cdot \Omega(\wv) + \frac{1}{m} \sum_{i \in [m]} l(y_i, f(\xv_i)) \end{align*} $$

  • 线性模型:$f(\xv) = \wv^\top \xv + b$
  • Hinge 损失:$l(y, f(\xv)) = \max \{ 0, 1 - y f(\xv) \}$
  • 正则化项:$\ell_2$正则

$$ \begin{align*} \min_{\wv,b} & ~ \frac{1}{2} \| \wv \|_2^2 + \frac{\lambda}{m} \sum_{i \in [m]} \max \{ 0, 1 - y_i (\wv^\top \xv_i + b) \} \\ & \class{blue}{\bigg \Downarrow ~ \max \{ 0, 1 - y_i (\wv^\top \xv_i + b) \} = \epsilon_i} \\ \min_{\wv,b} & ~ \frac{1}{2} \| \wv \|_2^2 + \frac{\lambda}{m} \sum_{i \in [m]} \epsilon_i, \quad \st ~ y_i (\wv^\top \xv_i + b) \geq 1 - \epsilon_i, ~ \epsilon_i \geq 0 \end{align*} $$


支持向量机

$n \gg m$时,求解支持向量机对偶问题更为方便

$$ \begin{align*} \min_{\alphav} ~ \frac{1}{2} \alphav^\top \Yv \Xv \Xv^\top \Yv \alphav - \ev^\top \alphav \quad \st ~ \zerov \leq \alphav \leq \frac{\lambda}{m} \ev, ~ \yv^\top \alphav = 0 \end{align*} $$


支持向量机的解法比较多

  • 原问题:(随机) 次梯度下降,割平面法
  • 对偶问题:SMO,坐标下降

支持向量机 vs. 感知机

  • 共同点:解具有稀疏性,即$\wv$只与少数样本 (支持向量) 有关
  • 支持向量机的泛化能力有严格理论保证,感知机没有
  • 支持向量机的分类超平面是唯一且确定的,位于两类样本的正中间,对数据采样较为鲁棒,感知机求得的分类超平面不唯一,依赖样本顺序

支持向量回归

正则化项 + 损失函数:

$$ \begin{align*} \min_\wv ~ \lambda \cdot \Omega(\wv) + \frac{1}{m} \sum_{i \in [m]} l(y_i, f(\xv_i)) \end{align*} $$

  • 线性模型:$f(\xv) = \wv^\top \xv + b$
  • $\epsilon$-不敏感损失:$l(y, f(\xv)) = \max \{ 0, |y - f(\xv)| - \epsilon \}$
  • 正则化项:$\ell_2$正则

$$ \begin{align*} \min_{\wv,b} ~ \frac{1}{2} \| \wv \|_2^2 + \frac{\lambda}{m} \sum_{i \in [m]} \max \{ 0, |\wv^\top \xv_i + b - y_i| - \epsilon \} \end{align*} $$

  • Hinge 损失在部分区域可以取零值,这使得支持向量机的解具有稀疏性,只与产生损失的那些样本 (支持向量) 有关
  • 推广到回归问题就是支持向量回归,故$\epsilon$-不敏感损失也要在部分区域取零值

对数几率回归

正则化项 + 损失函数:

$$ \begin{align*} \min_\wv ~ \lambda \cdot \Omega(\wv) + \frac{1}{m} \sum_{i \in [m]} l(y_i, f(\xv_i)) \end{align*} $$

  • 线性模型:$f(\xv) = \wv^\top \xv + b$
  • 对数几率损失:$l(y, f(\xv)) = \log (1 + \exp (- y f(\xv)))$
  • 正则化项:$\ell_2$正则

$$ \begin{align*} \min_{\wv,b} ~ \frac{1}{2} \| \wv \|_2^2 + \frac{\lambda}{m} \sum_{i \in [m]} \log (1 + \exp (- y_i (\wv^\top \xv_i + b))) \end{align*} $$

初衷:

  • 让分类器的输出结果具有自然的概率意义
  • 支持向量机的输出若想具有概率意义,还需进行额外的后处理

对数几率回归

引入从预测值到概率的映射$\sigma: \Rbb \mapsto [0,1]$

$$ \begin{align*} \sigma(z) = \frac{1}{1 + \exp (-z)} = \begin{cases} 1 & z \rightarrow \infty \\ 0 & z \rightarrow -\infty \end{cases}, ~ 1 - \sigma(z) = \frac{1}{1 + \exp (z)} = \sigma(-z) \end{align*} $$

  • 设预测$\xv$为正类的概率$p(y=1|\xv) = \sigma(\wv^\top \xv + b)$
  • 预测$\xv$为负类的概率$p(y=-1|\xv) = 1 - \sigma(\wv^\top \xv + b) = \sigma(-\wv^\top \xv-b)$
  • 预测结果分布可记为$\pv = [\sigma(\wv^\top \xv + b); \sigma(-\wv^\top \xv-b)]$
  • 由于$y \in \{ \pm 1 \}$,真实类别分布可记为$\qv = [\frac{1+y}{2}; \frac{1-y}{2}]$
  • 分布$\pv$$\qv$之间的差异可作为替代损失

问题:给定分布$\qv$,如何度量分布$\pv$与它之间的差异?


交叉熵$H_{\qv} (\pv) = - \sum_i q_i \log p_i = \sum_i q_i \log (1/p_i)$,当$\pv = \qv$时交叉熵最小


对数几率回归

$$ \begin{align*} \min_{\pv} ~ H_{\qv} (\pv) = - \sum_i q_i \log p_i = \sum_i q_i \log (1/p_i), \quad \st ~ \sum_i p_i = 1 \end{align*} $$

拉格朗日函数为$L = - \sum_i q_i \log p_i + \alpha (\sum_i p_i - 1)$,于是

$$ \begin{align*} \frac{\partial L}{\partial p_i} = - \frac{q_i}{p_i} + \alpha = 0 ~ \Longrightarrow ~ p_i = \frac{q_i}{\alpha} ~ \Longrightarrow ~ \alpha = 1 ~ \Longrightarrow ~ p_i = q_i \end{align*} $$


对数几率回归:$\qv = [\frac{1+y}{2}; \frac{1-y}{2}]$$\pv = [\sigma(\wv^\top \xv + b); \sigma(-\wv^\top \xv-b)]$

$$ \begin{align*} H_{\qv} (\pv) & = \frac{1+y}{2} \log (1 + \exp (-\wv^\top \xv - b)) + \frac{1-y}{2} \log (1 + \exp (\wv^\top \xv + b)) \\ & = \begin{cases} \log (1 + \exp (-\wv^\top \xv - b)) & y = 1 \\ \log (1 + \exp (\wv^\top \xv + b)) & y = -1 \end{cases} \\ & = \log (1 + \exp (- y (\wv^\top \xv + b))) \end{align*} $$


对数几率回归

$$ \begin{align*} H_{\qv} (\pv) = \log (1 + \exp (- y (\wv^\top \xv + b))) \end{align*} $$


交叉熵损失应用到二分类问题上就退化成了对数几率损失

$p_+ = p(y=1|\xv)$$p_- = p(y=-1|\xv) = 1 - p_+$,则

$$ \begin{align*} p_+ = \frac{1}{1 + \exp (-(\wv^\top \xv + b))} ~ \Longrightarrow ~ \wv^\top \xv + b = \ln \frac{p_+}{1-p_+} = \ln \frac{p_+}{p_-} \end{align*} $$

  • $p_+$$p_-$的比值反映了预测为正类的相对可能性,称为几率
  • 用线性模型$\wv^\top \xv + b$拟合几率的对数$\ln (p_+/p_-)$,故称为对数几率回归
  • 虽然名为回归,但本质上是一个分类模型
  • 让预测结果具有概率意义的代价是牺牲了解的稀疏性,预测的计算开销更大
  • 对数几率回归另一个优势是可以很自然地推广到多分类

多分类对数几率回归

设共有$C$个类,预测函数$f(\xv) = \argmax_{c \in [C]} (\wv_c^\top \xv + b_c)$

引入$\Rbb^C \mapsto \Delta^C$的 Softmax 映射:

$$ \begin{align*} p(y = c | \xv) & = \frac{\exp (\wv_c^\top \xv + b_c)}{\sum_{c' \in [C]} \exp (\wv_{c'}^\top \xv + b_{c'})} \\ & = \frac{\exp ((\wv_c - \wv_C)^\top \xv + b_c - b_C)}{\sum_{c' \in [C-1]} \exp ((\wv_{c'} - \wv_C)^\top \xv + b_{c'} - b_C) + 1} \end{align*} $$

$\wv_c \leftarrow \wv_c - \wv_C$$b_c \leftarrow b_c - b_C$,记$p_c = p(y = c | \xv)$,于是

$$ \begin{align*} p_c = \frac{\exp (\wv_c^\top \xv + b_c)}{\sum_{c' \in [C-1]} \exp (\wv_{c'}^\top \xv + b_{c'}) + 1}, \quad p_C = 1 - \sum_{c' \in [C-1]} p_c \end{align*} $$


多分类对数几率回归

$$ \begin{align*} p_c = \frac{\exp (\wv_c^\top \xv + b_c)}{\sum_{c' \in [C-1]} \exp (\wv_{c'}^\top \xv + b_{c'}) + 1}, \quad p_C = 1 - \sum_{c' \in [C-1]} p_c \end{align*} $$

对于样本$(\xv_i, y_i)$$\qv_i = [1_{y_i=1}, 1_{y_i=2}, \ldots, 1_{y_i=C}]$$y_i$的独热编码

$$ \begin{align*} \pv_i & = [p_1, \ldots, p_{C-1}, p_C] = \frac{[ \exp (\wv_1^\top \xv_i + b_1), \ldots, \exp (\wv_{C-1}^\top \xv_i + b_{C-1}), 1 ]}{\sum_{c' \in [C-1]} \exp (\wv_{c'}^\top \xv_i + b_{c'}) + 1} \end{align*} $$

采用交叉熵$H_{\qv_i} (\pv_i)$作为替代损失可得多分类对数几率回归

$$ \begin{align*} \min_{\wv_c, b_c} & ~ \frac{1}{2} \sum_{c \in [C-1]} \| \wv_c \|_2^2 + \frac{\lambda}{m} \sum_{i \in [m]} \sum_{c \in [C]} [\qv_i]_c \log \frac{1}{[\pv_i]_c} \end{align*} $$


多分类对数几率回归

$C = 2$

$$ \begin{align*} H_{\qv} (\pv) & = - 1_{y=1} \log \frac{\exp (\wv_1^\top \xv + b_1)}{ \exp (\wv_1^\top \xv + b_1) + 1} - 1_{y=2} \log \frac{1}{ \exp (\wv_1^\top \xv + b_1) + 1} \\ & = 1_{y=1} \log (1 + \exp (- \wv_1^\top \xv - b_1)) + 1_{y=2} \log (1 + \exp (\wv_1^\top \xv + b_1)) \end{align*} $$

将第$2$类类别标记记为$-1$,则$H_{\qv} (\pv) = \log (1 + \exp (- y (\wv_1^\top \xv + b_1)))$


神经网络视角:

对数几率回归 层数 激活函数 输出层节点数 类别标记
二分类 1 层 Logistic $1$ $y \in \{ 1, -1 \}$
多分类 1 层 Softmax $C$ $y \in [C]$

小结

正则化项 + 损失函数:

$$ \begin{align*} \min_\wv ~ \lambda \cdot \Omega(\wv) + \frac{1}{m} \sum_{i \in [m]} l(y_i, f(\xv_i)) \end{align*} $$

模型 正则化项 损失函数 预测函数
线性回归 - $(\wv^\top \xv + b - y)^2$ $\wv^\top \xv + b$
岭回归 $\|\wv\|_2^2$ $(\wv^\top \xv + b - y)^2$ $\wv^\top \xv + b$
LASSO $\|\wv\|_1$ $(\wv^\top \xv - y)^2$ $\wv^\top \xv$
感知机 - $\max \{ 0, - y \wv^\top \xv \}$ $\sgn(\wv^\top \xv)$
支持向量机 $\|\wv\|_2^2$ $\max \{ 0, 1 - y (\wv^\top \xv + b) \}$ $\sgn(\wv^\top \xv + b)$
支持向量回归 $\|\wv\|_2^2$ $\max \{ 0, \wv^\top \xv + b - y - \epsilon \}$ $\wv^\top \xv + b$
对数几率回归 $\|\wv\|_2^2$ $\log (1 + \exp (- y (\wv^\top \xv + b)))$ $\sigma(\wv^\top \xv + b)$

以上线性模型均可通过引入核映射实现非线性预测能力